import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:二叉树层序遍历、对称二叉树、二叉树最近公共祖先（非递归）、由前序和中序构造二叉树
 * Date: 2024-02-04
 * Time:1:48
 */
public class Solution1 {
     public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

    Queue<TreeNode> queue = new LinkedList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)
            return new ArrayList<>();

        List<List<Integer>> ret = new ArrayList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();

            //这个循环实现：将第k层的元素出队列，让第k+1层元素入队
            while(size-- > 0) {
                TreeNode top = queue.poll();  //取当前队头的元素
                list.add(top.val);
                if(top.left != null)
                    queue.offer(top.left);
                if(top.right != null)
                    queue.offer(top.right);
            }
            ret.add(list);
        }
        return ret;
    }
/////////////////////////////////////////////////////
    //对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        return Symmetric(root.left,root.right);
    }

    public boolean Symmetric(TreeNode root1,TreeNode root2) {
        //整体思路是前序遍历，先对根节点进行判断
        if(root1 == null && root2 == null) {
            return true;
        }
        //到这里，root1和root2至少有一个不为空，接下来判断有没有一个是空的，若有，那就不是对称的了
        if(root1 == null || root2 == null) {
            return false;
        }
        //到这里，root1和root2都不为空
        //比较根节点的值
        if(root1.val != root2.val) {
            return false;
        } else {
            //从else开始就是遍历根节点的左子树和右子树
            boolean ret1 = Symmetric(root1.left,root2.right);
            boolean ret2 = Symmetric(root1.right,root2.left);
            if(ret1 && ret2) {
                return true;
            } else {
                return false;
            }
        }
    }

    //////////////////////////////////////////////////////
    //二叉树最近公共祖先（非递归）
    //借助两个栈，将从根节点到p或q的沿途节点存进栈
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();

    //node：要查找的节点
    public TreeNode findPath(TreeNode root,TreeNode node,Stack<TreeNode> stack) {
        if(root == null)
            return null;
        if(root == node)
            return root;

        //前序遍历
        stack.push(root);
        TreeNode ret1 = findPath(root.left,node,stack);
        TreeNode ret2 = findPath(root.right,node,stack);

        //左右都为空，出栈
        if(ret1 == null && ret2 == null) {
            stack.pop();
            return null;
        } else if(ret1 == null && ret2 != null) {
            return ret2;
        } else if(ret1 != null && ret2 == null) {
            return ret1;
        }
        return root;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ret1 = findPath(root,q,stack1);
        TreeNode ret2 = findPath(root,p,stack2);


        return null;
    }
/////////////////////////////////////////////
    public int prei;   //
    public int Begini; //区间起始下标
    public int Endi;   //区间终止下标

    public void preTravel(TreeNode root) {
        if(root == null)
            return;
        System.out.println(root.val);
        preTravel(root.left);
        preTravel(root.right);
    }



    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //int index = findIndex(preorder[0],inorder);
        return devide(preorder,inorder,0,inorder.length - 1);
    }

    //val：要找的根节点的值
    public int findIndex(int val,int[] inorder) {
        for(int i = 0;i < inorder.length;i++) {
            if(inorder[i] == val) {
                return i;  //返回它在inorder中的下标
            }
        }
        return -1;
    }

    public TreeNode devide(int[] preorder,int[] inorder,int begin,int end) {
        if(end < begin)
            return null;

        //从中序遍历数组中找到“分割点”
        int dev = findIndex(preorder[prei++],inorder);  //dev：分割点在inorder中的下标
        //分割点就是根节点
        TreeNode node = new TreeNode(inorder[dev]);
        //通过递归连接左右子树
        node.left = devide(preorder,inorder,begin,dev-1);
        node.right = devide(preorder,inorder,dev+1,end);
        return node;

    }

    //index：根节点下标
/*
    public TreeNode devide(int[] preorder,int[] inorder,int index,int Begini,int Endi) {
//        if(index < Begini || index > Endi)
//            return null;
        if(Begini > Endi)
            return null;

        int val = preorder[prei];
        prei++;
        TreeNode node = new TreeNode(val);
        index = findIndex(val,inorder);
        if(index >= Begini) {
            node.left = devide(preorder, inorder, index, 0, index - 1);
        }
        if(index <= Endi) {
            node.right = devide(preorder, inorder, index, index + 1, inorder.length - 1);
        }
        return node;
    }
*/

}
